Edit distance

Time: O(MxN); Space: O(M+N); hard

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character

  2. Delete a character

  3. Replace a character

Example 1:

Input: word1 = “horse”, word2 = “ros”

Output: 3

Explanation:

  • horse -> rorse (replace ‘h’ with ‘r’)

  • rorse -> rose (remove ‘r’)

  • rose -> ros (remove ‘e’)

Example 2:

Input: word1 = “intention”, word2 = “execution”

Output: 5

Explanation:

  • intention -> inention (remove ‘t’)

  • inention -> enention (replace ‘i’ with ‘e’)

  • enention -> exention (replace ‘n’ with ‘x’)

  • exention -> exection (replace ‘n’ with ‘c’)

  • exection -> execution (insert ‘u’)

[1]:

class Solution1(object):
    """
    Time: O(N*M)
    Space: O(N+M)
    """
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if len(word1) < len(word2):
            return self.minDistance(word2, word1)

        distance = [i for i in range(len(word2) + 1)]

        for i in range(1, len(word1) + 1):
            pre_distance_i_j = distance[0]
            distance[0] = i
            for j in range(1, len(word2) + 1):
                insert = distance[j - 1] + 1
                delete = distance[j] + 1
                replace = pre_distance_i_j
                if word1[i - 1] != word2[j - 1]:
                    replace += 1
                pre_distance_i_j = distance[j]
                distance[j] = min(insert, delete, replace)

        return distance[-1]

[2]:

s = Solution1()

word1 = "horse"
word2 = "ros"
assert s.minDistance(word1, word2) == 3

word1 = "intention"
word2 = "execution"
assert s.minDistance(word1, word2) == 5

[3]:

class Solution2(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        distance = [[i] for i in range(len(word1) + 1)]
        distance[0] = [j for j in range(len(word2) + 1)]

        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                insert = distance[i][j - 1] + 1
                delete = distance[i - 1][j] + 1
                replace = distance[i - 1][j - 1]
                if word1[i - 1] != word2[j - 1]:
                    replace += 1
                distance[i].append(min(insert, delete, replace))

        return distance[-1][-1]

[4]:

s = Solution2()

word1 = "horse"
word2 = "ros"
assert s.minDistance(word1, word2) == 3

word1 = "intention"
word2 = "execution"
assert s.minDistance(word1, word2) == 5